1. Field of the Invention
Embodiments of the invention relate to the field of error correction technology, and more specifically, to Reed-Solomon code.
2. Description of Related Art
The Reed-Solomon code is a block-based error correcting code with a wide range of applications in digital communications and storage. It is typically used to correct errors in many systems including: storage devices (e.g., tape, compact disk, digital vide disk, barcodes, etc), wireless or mobile communications (e.g., cellular telephones, microwave links, etc), satellite communications, digital television, and high-speed modems. A Reed-Solomon codeword is generated using a special polynomial. All valid code-words are exactly divisible by the generator polynomial. A Reed-Solomon decoder attempts to identify the position and magnitude of up to t errors (or 2t erasures) and to correct the errors or erasures. Finding the symbol error locations typically involves solving simultaneous equations with t unknowns. In general, this includes finding an error locator polynomial and finding the symbol error values. Techniques to do this include the Berlekamp-Massey procedure to find the error-locator polynomial, the Chien search to determine the error positions by finding the zeros of the error locator polynomial, and the Forney algorithm to compute the error values. These techniques typically require evaluation of a polynomial at certain points.
Existing techniques to evaluate polynomial at certain points have a number of disadvantages. A popular technique is the Horner scheme. For a polynomial of degree n−1 and t roots, the Horner scheme needs tn additions and tn multiplications. The amount of computations may be high for many high-speed applications.